1. Technical Field
The present teaching relates to methods, systems, and programming for information retrieval. Particularly, the present teaching is directed to methods, systems, and programming for searching encrypted data.
2. Discussion of Technical Background
Cloud services are effective to seamlessly deploy end-to-end encryption for communications, e.g. with end-to-end encrypted messaging protocols like IMessage or Whatsapp. Video teleconferences can also be secured. Unlike chat and video, email is not ephemeral; but it is archived, stored, and searched for years. End-to-end encryption for email implies that the mail servers will not know the decryption key for decrypting emails. Search is an important feature for email, including encrypted email. As most users typically cannot store years of email on their devices, they opt instead to store their emails in the cloud, which poses a major obstetrical to end-to-end encrypted mail.
Existing solutions for searching encrypted emails include symmetric searchable encryption (SSE) where the server stores an encrypted index for mapping keywords to a list of documents or emails they appear in. But these solutions cannot reach a necessary input/output (IO) efficiency without leaking significantly more information on sent/received emails. To date, all dynamic search schemes store updates to the index in memory due to extremely high IO load. For cloud based systems with hundreds of millions of users each with a distinct index, this is not feasible. Simply storing data in disk is not feasible either, as existing non-encrypted search already reaches an IO bound.
Therefore, there is a need to develop techniques to search for encrypted data to overcome the above drawbacks.